package com.caoyanan.algorithm.question.zuoTraining.training004.class01;

import com.caoyanan.algorithm.question.zuoTraining.LogarithmInputGenerator;

/**
 * 删字符得到另一个字符串
 * 给定两个字符串S和T，返回S子序列等于T  的个数有多少
 *  也就是S字符串 删除一些字符 得到T，删除方案的个数
 * @author: caoyanan
 * @time: 2021/6/4 2:50 下午
 */
public class Question07_DeleteCharToStringT {

    public static void main(String[] args) {

        int count = 1000;
        for (int i = 0; i < count; i++) {
            String s = LogarithmInputGenerator.getInstance()
                    .generateLowerLetterString(5, 3);
            String t = "" + s.charAt(1) + s.charAt(3);
            Integer answer = deleteSCharToTChar(s, t);
            System.out.printf("字符串 %s 删除一些字符得到 %s 共有 %s 种方案 \n", s, t, answer);

        }
    }

    /**
     * 从字符串s删一些字符得到的子序列 等于字符t，可以有多少种删字符的方式
     * 这道题属于动态规划经典模型中的  一个样本做行、一个样本做列的对应模型
     * dp[i][j] 表示字符串 s前i个字符的子串 有多少种删字符方式得到的子序列 等于 t前j个字符的子串
     * 首先第一行 dp[i][0] s前i个字符的子串， 怎么删 得到 0个字符的t子串，答案是1种，全删了
     * 第一列 dp[0][j]，s前0个字符的子串 ，怎么删 能够得到 j个字符的t子串，答案是0种， 怎么删都得不到 (dp[0][0] = 1)
     *
     * 对于一个普遍位置dp[i][j]。
     * 如果 s[i] != t[j]，那么t的最后一个字符一定要靠s前面的字符搞定了 dp[i-1][j]
     * 如果 s[i] == t[j],t最后一个字符可以由s的最后一个字符搞定，也就是 dp[i-1][j-1],
     *      t最后一个字符也可以被s前面的字符搞定，也就是 dp[i-1][j]
     * @param s
     * @param t
     * @return
     */
    private static Integer deleteSCharToTChar(String s, String t) {

        // 输入不合法
        if (s == null || t == null) {
            return Integer.MIN_VALUE;
        }
        int[][] dp = new int[s.length()+1][t.length()+1];

        // 第一行
        for (int j = 0; j < t.length(); j++) {
            dp[0][j] = 0;
        }
        // 第一列
        for (int i = 0; i < s.length(); i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= t.length(); j++) {
                dp[i][j] = dp[i-1][j] + (s.charAt(i-1) == t.charAt(j-1) ? dp[i-1][j-1] : 0);
            }
        }
        return dp[s.length()][t.length()];
    }
}
